/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class ShortestPathtoGetAllKeys {
	public int shortestPathAllKeys(String[] grid) {
		int n = grid.length;
		int m = grid[0].length();
		char[][] G = new char[n][m];
		int[] start = new int[2];
		start[0] = start[1] = -1;
		int k = 0;
		for (int i = 0; i < G.length; i++) {
			G[i] = grid[i].toCharArray();
			for (int j = 0; j < m; j++) {
				if (G[i][j] == '@') {
					start[0] = i;
					start[1] = j;
				} else if (Character.isLowerCase(G[i][j])) {
					k = Math.max(k, G[i][j] - 'a' + 1);
				}
			}
		}
		int fullKeys = (1 << k) - 1;
		Set<String> visited = new HashSet<>();
		Queue<String> status = new LinkedList<>();
		String sta = toStr(start[0], start[1], 0);
		visited.add(sta);
		status.add(sta);
		int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		int step = 0;
		while (!status.isEmpty()) {
			int size = status.size();
			step++;
			for (int j = 0; j < size; j++) {
				String string = status.poll();
				String[] strings = string.split("_");
				int x = Integer.parseInt(strings[0]);
				int y = Integer.parseInt(strings[1]);
				int keys = Integer.parseInt(strings[2]);
				// 向四周
				for (int i = 0; i < dir.length; i++) {
					int newX = x + dir[i][0];
					int newY = y + dir[i][1];
					if (newX < n && newX >= 0 && newY < m && newY >= 0 && G[newX][newY] != '#') {// 可以访问的四个邻居
						int curKeys = keys;
						if (Character.isLowerCase(G[newX][newY])) {// 如果有钥匙，则捡起来
							// 小写字母，捡起钥匙
							int key = G[newX][newY] - 'a';
							curKeys |= (1 << key);
							if (curKeys == fullKeys) {
								return step;
							}
						} else if (Character.isUpperCase(G[newX][newY])) { // 如果有钥匙，则可以通过；否则不可以
							int key = G[newX][newY] - 'A';
							if ((keys & (1 << key)) == 0) {
								continue;
							}
						}
						// 如果是.，则直接通过
						// 把新的状态加入待处理列表
						String newStatu = toStr(newX, newY, curKeys);
						if (visited.add(newStatu)) {
							status.add(newStatu);
						}
					}
				}
			}

		}
		return -1;
	}

	private String toStr(int i, int j, int k) {
		return i + "_" + j + "_" + k;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] grid = { "@..aA", "..B#.", "....b" };
		System.out.println(new ShortestPathtoGetAllKeys().shortestPathAllKeys(grid));
	}

}
